package com.zhanghp.class022;

/**
 * 翻转对数量
 * 测试链接 : https://leetcode.cn/problems/reverse-pairs/
 *
 * @author zhanghp
 * @since 2024/3/6 17:52
 */
public class Code02_ReversePairs {

    public static int max = 50_001;

    public static int[] help = new int[max];

    class Solution {
        public int reversePairs(int[] nums) {
            if (nums == null || nums.length <= 1) {
                return 0;
            }
            return reverse(nums, 0, nums.length - 1);
        }

        public int reverse(int[] nums, int l, int r) {
            if (l == r) {
                return 0;
            }
            int m = l + ((r - l) >> 1);
            return reverse(nums, l, m) + reverse(nums, m + 1, r) + merge(nums, l, m, r);
        }

        public int merge(int[] arr, int l, int m, int r) {

            // 处理
            int ans = 0;
            for (int i = l, j = m + 1; i <= m; i++) {
                while (j <= r && arr[i] > ((long) arr[j] << 1)) {
                    j++;
                }
                // j++会过界，所以-1
                // j是索引下标，要得到次数，要减掉中间的m
                ans += j - m - 1;
            }

            // 排序
            int a = l, i = l, b = m + 1;
            while (a <= m && b <= r) {
                help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
            }
            while (a <= m) {
                help[i++] = arr[a++];
            }
            while (b <= r) {
                help[i++] = arr[b++];
            }
            for (i = l; i <= r; i++) {
                arr[i] = help[i];
            }
            return ans;
        }

        public int merge2(int[] arr, int l, int m, int r) {

            int ans = 0;
            for (int i = l, j = m + 1, count = 0; i <= m; i++) {
                while (j <= r && (long) arr[i] > ((long) arr[j] << 1)) {
                    j++;
                    count++;
                }
                ans += count;
            }

            // 排序
            int a = l, b = m + 1, i = l;
            while (a <= m && b <= r) {
                help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
            }
            while (a <= m) {
                help[i++] = arr[a++];
            }

            while (b <= r) {
                help[i++] = arr[b++];
            }
            for (i = l; i <= r; i++) {
                arr[i] = help[i];
            }
            return ans;

        }
    }
}
